package exercise;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution14 {
    public List<Integer> findAnagrams(String ss, String pp) {
        if(ss.length() < pp.length()) {
            return new ArrayList<>();
        }
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        List<Integer> ans = new ArrayList<>();
        int l = 0, r = 0, len = s.length;
        int[] shush = new int[26];
        int[] phush = new int[26];
        for (char ch : p) {
            phush[ch-'a']++;
        }
        while (r-l < p.length) {
            shush[s[r++]-'a']++;
        }
        
        // System.out.println(ss.substring(l, r) + " " + Arrays.toString(shush) + l + " " + r);

        if (Arrays.equals(shush, phush)) {
            ans.add(l);
        }
        while (r < len) {
            shush[s[r]-'a']++;
            shush[s[l++]-'a']--;
            // System.out.println(ss.substring(l, r+1) + " " + Arrays.toString(shush) + l + " " + r);
            if (Arrays.equals(shush, phush)) {
                ans.add(l);
            }
            r++;
        }
        return ans;
    }
}